﻿#define _CRT_SECURE_NO_WARNINGS 1
/**无重复字符串的排列组合。编写一种方法，计算某字符串的所有排列组合，字符串每个字符均不相同。
* Note: The returned array must be malloced, assume caller calls free().
*/
//void ba(char* S, char* p, char* v, int len, int d, char** ret, int* returnSize)
//{
//	if (d == len)
//	{
//		int retindex = (*returnSize)++;
//		ret[retindex] = malloc(len + 1);
//		memcpy(ret[retindex], p, len + 1);
//		return;
//	}
//	for (int i = 0; i<len; i++)
//	{
//		if (v[i])
//		{
//			continue;
//		}
//		v[i] = 1;
//		p[d] = S[i];
//		ba(S, p, v, len, d + 1, ret, returnSize);
//		v[i] = 0;
//	}
//}
//int fa(int per, int n)
//{
//	if (n <= 1)
//	{
//		return per;
//	}
//	return fa(per*n, n - 1);
//}
//char** permutation(char* S, int* returnSize){
//	int len = strlen(S);
//	int retsize = fa(1, len);
//	char** ret = calloc(retsize, sizeof(char*));
//	char* p = malloc(len + 1);
//	p[len] = 0;
//	char* v = malloc(len + 1);
//	memset(v, 0, len + 1);
//	*returnSize = 0;
//	ba(S, p, v, len, 0, ret, returnSize);
//	assert(*returnSize == retsize);
//	return ret;
//}












/**幂集。编写一种方法，返回某集合的所有子集。集合中不包含重复的元素。

说明：解集不能包含重复的子集。
* Return an array of arrays of size *returnSize.
* The sizes of the arrays are returned as *returnColumnSizes array.
* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
*/
//int** subsets(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){
//	int top = -1;
//	int* p = (int*)malloc(sizeof(int)*(1 << numsSize));
//	int** a = (int**)malloc(sizeof(int*)*(1 << numsSize));
//	int x = 0;
//	*returnSize = 1 << numsSize;
//	p[++top] = 0;
//	for (int i = 0; i<numsSize; i++)
//	{
//		x = top;
//		for (int j = 0; j <= x; j++)
//		{
//			a[++top] = (int*)malloc(sizeof(int)*(p[j] + 1));
//			p[top] = p[j] + 1;
//			for (int k = 0; k<p[j]; k++)
//			{
//				a[top][k] = a[j][k];
//			}
//			a[top][p[j]] = nums[i];
//		}
//	}
//	*returnColumnSizes = p;
//	return a;
//}









/**括号。设计一种算法，打印n对括号的所有合法的（例如，开闭一一对应）组合。

说明：解集不能包含重复的子集。
* Note: The returned array must be malloced, assume caller calls free().
*/
//#define MAX 10000
//void dfs(int lcnt, int rcnt, int n, char*str, int slen, char** a, int* size)
//{
//	if ((lcnt<rcnt) || (lcnt>n) || (rcnt>n))
//	{
//		return;
//	}
//	if (slen == (2 * n))
//	{
//		a[*size] = (char*)malloc((strlen(str) + 1)*sizeof(char));
//		strcpy(a[*size], str);
//		(*size)++;
//		return;
//	}
//	str[slen] = '(';
//	dfs(lcnt + 1, rcnt, n, str, slen + 1, a, size);
//	str[slen] = ')';
//	dfs(lcnt, rcnt + 1, n, str, slen + 1, a, size);
//	return;
//}
//char** generateParenthesis(int n, int* returnSize){
//	char** a = (char**)malloc(sizeof(char*)*MAX);
//	char str[MAX] = { '\0' };
//	int size = 0;
//	dfs(0, 0, n, str, 0, a, &size);
//	*returnSize = size;
//	return a;
//}









/**编写函数，实现许多图片编辑软件都支持的「颜色填充」功能。

待填充的图像用二维数组 image 表示，元素为初始颜色值。初始坐标点的行坐标为 sr 列坐标为 sc。需要填充的新颜色为 newColor 。

「周围区域」是指颜色相同且在上、下、左、右四个方向上存在相连情况的若干元素。

请用新颜色填充初始坐标点的周围区域，并返回填充后的图像。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/color-fill-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
* Return an array of arrays of size *returnSize.
* The sizes of the arrays are returned as *returnColumnSizes array.
* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
*/
//void dfs(int** image, int row, int col, int r, int c, int newColor, int old)
//{
//	if (r<0 || c<0 || r >= row || c >= col)
//	{
//		return;
//	}
//	int a = image[r][c];
//	if (a == old&&a != newColor)
//	{
//		image[r][c] = newColor;
//		dfs(image, row, col, r - 1, c, newColor, old);
//		dfs(image, row, col, r + 1, c, newColor, old);
//		dfs(image, row, col, r, c - 1, newColor, old);
//		dfs(image, row, col, r, c + 1, newColor, old);
//	}
//
//}
//int** floodFill(int** image, int imageSize, int* imageColSize, int sr, int sc, int newColor, int* returnSize, int** returnColumnSizes){
//	dfs(image, imageSize, imageColSize[0], sr, sc, newColor, image[sr][sc]);
//	*returnSize = imageSize;
//	*returnColumnSizes = imageColSize;
//	return image;
//}









//硬币。给定数量不限的硬币，币值为25分、10分、5分和1分，编写代码计算n分有几种表示法。(结果可能会很大，你需要将结果模上1000000007)
//int waysToChange(int n){
//	int div[] = { 5, 10, 25 };
//	int dp[n + 1];
//	for (int i = 0; i <= n; i++)
//	{
//		dp[i] = 1;
//	}
//	for (int j = 0; j<3; j++)
//	{
//		for (int k = 0; k <= n - div[j]; k++)
//		{
//			dp[k + div[j]] += dp[k];
//			dp[k + div[j]] %= 1000000007;
//		}
//	}
//	return dp[n];
//}










//
//搜索旋转数组。给定一个排序后的数组，包含n个整数，但这个数组已被旋转过很多次了，次数不详。请编写代码找出数组中的某个元素，假设数组元素原先是按升序排列的。若有多个相同元素，返回索引值最小的一个。
//int search(int* arr, int arrSize, int target){
//	int l = 0;
//	int r = arrSize - 1;
//	int m = 0;
//	while (l <= r)
//	{
//		m = l + ((r - l) >> 1);
//		if (arr[l]<arr[m])
//		{
//			if (arr[l] <= target&&target <= arr[m])
//			{
//				r = m;
//			}
//			else
//			{
//				l = m + 1;
//			}
//		}
//		else if (arr[l]>arr[m])
//		{
//			if (arr[m]<target&&target<arr[l])
//			{
//				l = m + 1;
//			}
//			else
//			{
//				r = m;
//			}
//		}
//		else
//		{
//			if (arr[l] == target)
//			{
//				return l;
//			}
//			else
//			{
//				l++;
//			}
//		}
//	}
//	return -1;
//}









/**编写一个函数，不用临时变量，直接交换numbers = [a, b]中a与b的值。
* Note: The returned array must be malloced, assume caller calls free().
*/
//int* swapNumbers(int* numbers, int numbersSize, int* returnSize){
//	numbers[0] = numbers[0] ^ numbers[1];
//	numbers[1] = numbers[0] ^ numbers[1];
//	numbers[0] = numbers[0] ^ numbers[1];
//	*returnSize = numbersSize;
//	return numbers;
//}









/**给定一个已按照 升序排列  的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。

函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 1 开始计数 ，所以答案数组应当满足 1 <= answer[0] < answer[1] <= numbers.length 。

你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
* Note: The returned array must be malloced, assume caller calls free().
*/
/*int* twoSum(int* numbers, int numbersSize, int target, int* returnSize){
	int* a = (int*)malloc(sizeof(int) * 2);
	*returnSize = 2;
	a[0] = a[1] = -1;
	int l = 0;
	int r = numbersSize - 1;
	while (l<r)
	{
		int m = numbers[l] + numbers[r];
		if (m == target)
		{
			a[0] = l + 1;
			a[1] = r + 1;
			return a;
		}
		else if (m<target)
		{
			l++;
		}
		else
		{
			r--;
		}
	}
	return a;
}*/	








//给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数
//void swp(int* a, int* b)
//{
//	int t = *a;
//	*a = *b;
//	*b = t;
//}
//void reverse(int* nums, int l, int r)
//{
//	while (l<r)
//	{
//		swp(&nums[l], &nums[r]);
//		l++;
//		r--;
//	}
//}
//void rotate(int* nums, int numsSize, int k){
//	k %= numsSize;
//	reverse(nums, 0, numsSize - 1);
//	reverse(nums, 0, k - 1);
//	reverse(nums, k, numsSize - 1);
//	return nums;
//}








//给定两个整数数组a和b，计算具有最小差绝对值的一对数值（每个数组中取一个值），并返回该对数值的差
//#define MAX_NUM(a)    ((a)>0?(a):-(a))
//#define MIN_NUM(a,b)  ((a)>(b)?(b):(a)) 
//int cmp(const void* a, const void* b)
//{
//	const int l = *(int*)a;
//	const int r = *(int*)b;
//	return l>r ? 1 : -1;
//}
//int smallestDifference(int* a, int aSize, int* b, int bSize){
//	qsort(a, aSize, sizeof(int), cmp);
//	qsort(b, bSize, sizeof(int), cmp);
//	long min = MAX_NUM((long)(a[0] - b[0]));
//	int i = 0;
//	int j = 0;
//	while (i<aSize&&j<bSize)
//	{
//		if (a[i]>b[j])
//		{
//			min = MIN_NUM(min, MAX_NUM((long)(a[i] - b[j])));
//			j++;
//		}
//		else if (a[i]<b[j])
//		{
//			min = MIN_NUM(min, MAX_NUM((long)(a[i] - b[j])));
//			i++;
//		}
//		else
//		{
//			return 0;
//		}
//	}
//	return min;
//}